會提到 Two Pointer，除了 LeetCode 有一個類別是 "Two Pointer"，另外認為很適合拿來入門刷題。因為剛開始刷題總是很容易朝著 Big O(n²) 方向想，例如以下

for (var i = 0; i < len - 1; i++) {
  for (var j = i + 1; j < len; j++) {
		...
	}
}

又或是

for(){
	包 map/indexOf/find 這樣基本上都是遍歷兩次 Big O(n²)
}

但使用 Two pointer 方向想，通常可以讓時間複雜度保持在 Big O(n)，直接拿例子來解釋好了

167. Two Sum II - Input array is sorted

// Question:
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

一開始我這樣想

 /**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(num, target) {
    const len = num.length;
    for(let i = 0; i< len; i++ ){
        var ind = num.indexOf(target - num[i]);
        if(ind !== -1 && i !== ind){
            return [i + 1, ind + 1].sort( (a,b) => a - b);
        }
    }
    return false;

};

for 一次、indexOf 一次。然後為了題目順序又 sort 一次。時間複雜度已是比 Big O (n²) 還差。難怪解出來是
Runtime: 400 ms, faster than 5.94% of JavaScript online submissions 效能超差

用 Two Pointer 方向想吧

Two pointer 直接翻譯就是兩個指針(廢話)，以這題來說就是 pointer 跟 ind，我們來想一下題目，題目說已經按照大小排好了

• num[pointer] + num[ind] < targer，兩個總和若太小則 pointer ++，讓他總和變大
  
• num[pointer] + num[ind] > targer，兩個總和若太大 ind -- ，讓他總和變小
  

完整程式碼

var twoSum = function(numbers, target) {
    let pointer = 0;
    let len = numbers.length
    let ind = len - 1
 
    while( target !== numbers[ind] + numbers[pointer]){
        target > numbers[ind] + numbers[pointer] ? pointer ++ : ind --;
    }
       
    return [pointer+1, ind+1];
};

最後幾天真的好難撐啊!! 尤其是假日真的是門檻。
剩兩天了啊~~ 加油加油

如有錯誤或需要改進的地方，拜託跟我說。
我會以最快速度修改，感謝您

歡迎追蹤我的部落格，除了技術文也會分享一些在矽谷工作的甘苦。